Skip to main content

Delete without Head Pointer

Problem​

You are given a node del_node of a Singly Linked List where you have to delete a value of the given node from the linked list, but you are not given the head of the list.

By deleting the node value, we mean that:

  • The value of the given node should not exist in the linked list.
  • The number of nodes in the linked list should decrease by one.
  • All the values before and after the del_node node should be in the same order.

Note:

  • Multiple nodes can have the same values as the del_node, but you must only remove the node whose pointer del_node is given to you.
  • It is guaranteed that there exists a node with a value equal to the del_node value, and it will not be the last node of the linked list.

Examples​

Example 1:

Input:
Linked List = 1 -> 2
del_node = 1
Output:
2

Explanation:
After deleting 1 from the linked list,
we have remaining nodes as 2.

Example 2:

Input:
Linked List = 10 -> 20 -> 4 -> 30
del_node = 20
Output:
10 4 30

Explanation:
After deleting 20 from the linked list,
we have remaining nodes as 10, 4, 30.

Your Task​

You don't need to read or print anything. You only need to complete the function deleteNode() which takes a reference of the deleting node value and your task is to delete the given node value.

Expected Time Complexity: O(1)O(1)
Expected Auxiliary Space: O(1)O(1)

Constraints​

  • 2≤n≤1032 ≤ n ≤ 10^3
  • 1≤elementsofthelinkedlist≤1091 ≤ elements of the linked list ≤ 10^9

Solution​

Approach​

To delete a node without a reference to the head pointer, we can mimic the effect of deleting the node by copying the value of the next node to the given node (del_node) and then deleting the next node.

Implementation​

class Solution:

def reverseDLL(self, head):
while head:
head.next, head.prev = head.prev, head.next
if not head.prev:return head
head=head.prev

Complexity Analysis​

  • Time Complexity: O(1)O(1), as the deletion operation requires constant time regardless of the size of the linked list.
  • Space Complexity: O(1)O(1), as the algorithm uses only a constant amount of extra space regardless of the input size.

References​